// == 场景 ==
// 假设我们是便利店的老板
// 准备各种面额的硬币 -> 找钱
// 硬币面额 [1, 5] 数量不限
// 他要找出去的钱 6

// == 问题 ==
// 在已有的硬币搭配下，可以提供的找钱的方法
// 例子中有 2 种： 1 + 5 或 6 x 1
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
// 计算找零钱的方法
// 动态规划 / 动态编程
// coins [10000, ] 10
int ways(vector<int> coins,int n) {
    vector<int> va(n + 1, 0);
    
    auto a = va.begin(); // Iterator 迭代器 位置
    auto b = va.begin();
    auto c = coins.begin();
    while (c != coins.end()) {
        for (int i = 0; i < n + 1 - *c; i++)
        {
            a = b;
            for (int j = 0; j < *c; j++)
            {
                a++;
            }
            *a = *a + *b;
            b++;
        }
        c++;
    }
    return (*(va.end() - 1));
}

int numberOfWaysToMakeChange(vector<int> coins, int n)
{
    // 创建一个包含 n+1 的元素的数组 ways，表达找从 0 至 n 钱的方法。
    // 并且将ways中每个元素初始化为0
    vector<int> ways(n + 1, 0);

    // ++++++中心思想++++++
    // 要计算n相对于面额k的找钱方法，只需计算n-k的相对于面额k的方法数，以此类推
    // 理解当面额k为面额数组k[k1,k2,...kn]时，那么计算n相对于面额数组k的找钱方法，只需计算n-k的相对于面额数组k的方法数，以此类推
    // ++++++中心思想++++++

    // 遍历所有的面额
    // 对于每一种面额，我们用它去遍历所有要找的钱数
    // 如果能找
    //    更新对应找钱上的方法数 ways[b(找钱)] + ways[b(找钱) - a(面额)]
    // 否则
    //    PASS
    // 所有面额遍历结束，ways 最后一个元素的值，就是答案

    //初始化ways[0]为1，表示找钱0即找开了，记1次
    ways[0] = 1;

    //循环每一种面额
    for (int j = 0; j < coins.size(); j++)
    {
        //循环计算1到n中所有数的相对于一种面额的找钱情况
        for (int i = 1; i <= n; i++)
        {
            //如果面额小于要找开的钱数
            if (coins[j] <= i)
            {
                //累加:把要找钱i的方法数和i-coins[j]的找钱方法数加起来
                ways[i] = ways[i] + ways[i - coins[j]];
            }
                
        }

        //打印每一种面额计算完成后ways中的值
        for (int k = 0; k < ways.size(); k++)
        {
            cout << k << "=" << ways[k] << endl;
        }

        //打印“--”用作分隔，便于查看ways中间值
        cout << "----------------------------------------" << endl;

    }
    
    //返回ways中最后一个元素的值，即是我们要计算要找钱n的方法数
    return (*(ways.end() - 1));
}

int main(int argc, char const *argv[])
{
  /* code */
  vector<int> coins{1, 5, 10, 25};
  cout<<numberOfWaysToMakeChange(coins, 10)<<endl;
  return 0;
}
